package 剑指offer;

public class _07重建二叉树 {
   public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

    //采用闭区间划分
    public TreeNode buildTree(int[] preorder, int preStart,int preEnd,
                              int[] inorder, int vinStart, int vinEnd){
        //4.递归出口
        if (preStart > preEnd || vinStart > vinEnd){
            return null;
        }
        //1.创建二叉树根节点，
        TreeNode root = new TreeNode(preorder[preStart]);
        //2.从中序遍历找根节点，
        for (int i = vinStart; i <= vinEnd; i++) {
            //说明在中序遍历中找到了根节点的位置[vinStart, i) [i+1, vinEnd]
            if (preorder[preStart] == inorder[i]){
                //3.重建左右子树
                root.left = buildTree(preorder, preStart + 1, preStart + i - vinStart,
                        inorder , vinStart, i - 1);
                root.right = buildTree(preorder, preStart + i - vinStart + 1, preEnd,
                        inorder, i + 1, vinEnd);
                break;
            }
        }
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length != inorder.length){
            return null;
        }
        return buildTree(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }
}
